#构建一颗二叉搜索树
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def generateTrees(start,end):
    if start>end:
        #表示当前的二叉搜索树位为空
        return [None,]
    allTrees=[]
    for i in range(start,end+1): #枚举可行的根节点
        #获得所有可行的左子树集合
        leftTrees=generateTrees(start,i-1)

        #获取所有可行的右子树集合
        rightTrees=generateTrees(i+1,end)

        #从左子树集合中选出一棵左子树,从右子树集合中选出一颗右子树,拼接到根节点上
        for l in leftTrees:
            for r in rightTrees:
                currTree=TreeNode(i)
                currTree.left=l
                currTree.right=r
                allTrees.append(currTree)
    return allTrees

def generateTree(n):

    return generateTrees(1,n)


print(generateTree(3))
